import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Stack;

public class LinkedDemo {
    public static void main(String[] args) {
        ListNode listnode1 = new ListNode(9);
        ListNode t = new ListNode(3);
        listnode1.next = t;
        t.next = new ListNode(7);

        ListNode listnode2 = new ListNode(6);
        listnode2.next = new ListNode(3);
//        ListNode result = ListAdd(listnode1,listnode2);
//        ListNode result = ListAdd2(listnode1,listnode2);
//        ListNode result = ListAdd3(listnode1,listnode2);
//        ListNode result = removeNthFromEnd(listnode1,2);
//        ListNode result = rotateLinkedList(listnode1,2);
        ListNode result = ReverseList(listnode1);
        while (result!=null){
            System.out.println("result.val = " + result.val);
            result = result.next;
        }

    }

    private static ListNode ReverseList(ListNode listnode1) {
        return null;
    }

    private static ListNode rotateLinkedList(ListNode head, int k) {
        // 转成数组，移动
        ArrayList<Integer> value = new ArrayList<>();
        while (head!=null){
            value.add(head.val);
            head = head.next;
        }
        int temp[] = new int[value.size()];
        for (int i = 0; i < value.size(); i++) {
            temp[(i+k)%value.size()] = value.get(i);
        }
        ListNode result = new ListNode(-1);
        ListNode pre = result;
        for (int i = 0; i < temp.length; i++) {
            pre.next = new ListNode(temp[i]);
            pre = pre.next;
        }
        return result.next;
    }

    private static ListNode removeNthFromEnd(ListNode listnode1, int i) {

        // 用栈保存
        Stack<ListNode> stack = new Stack<>();
        while (listnode1!=null){
            stack.add(listnode1);
            listnode1 = listnode1.next;
        }
        ListNode pre = null;
        int n = 0;
        Boolean flag = false;
        while (!stack.isEmpty()){
            ListNode pop = stack.pop();
            n++;
//            if(flag){
//                // 由于需要下一个，所以flag判断放在前面
//                pop.next = pre;
//                pre = pop;
//                flag = false;
//            }
//            if(n==i){
//                // d当前的不需要了,不用移动pre
//                flag = true;
//            }else
                if(n != i){
                pop.next = pre;
                pre = pop;
            }
        }
        return pre;
    }

    private static ListNode ListAdd3(ListNode listnode1, ListNode listnode2) {

        int flag = 0;
        // 用栈保存
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (listnode1!=null || listnode2!=null) {
            if(listnode1!=null){
                stack1.push(listnode1.val);
                listnode1 = listnode1.next;
            }
            if(listnode2!=null){
                stack2.push(listnode2.val);
                listnode2 = listnode2.next;
            }
        }
        Stack<Integer> res = new Stack<>();
        while (!stack1.isEmpty()||!stack2.isEmpty()){
            if(!stack1.isEmpty()){
                Integer pop = stack1.pop();
                flag += pop;
            }
            if(!stack2.isEmpty()){
                Integer pop = stack2.pop();
                flag += pop;
            }
            res.add(flag%10);
            flag = flag/10;
        }
        if(flag>0){
            res.add(1);
        }
        // 反转链表
        ListNode result = new ListNode(-1);
        ListNode pre = result;
        while (!res.isEmpty()){
            pre.next = new ListNode(res.pop());
            pre = pre.next;
        }
        return result.next;
    }

    private static ListNode ListAdd2(ListNode listnode1, ListNode listnode2) {

        int flag = 0;
        ListNode result = new ListNode(-1);
        ListNode pre = result;
        while (listnode1!=null || listnode2!=null){
            if(listnode1!=null){
                flag += listnode1.val;
                listnode1=listnode1.next;
            }
            if(listnode2!=null){
                flag += listnode2.val;
                listnode2 = listnode2.next;
            }
            pre.next = new ListNode(flag%10);
            flag = flag/10;
            pre = pre.next;
        }
        if(flag>0){
            pre.next = new ListNode(1);
        }
        return result.next;
    }

    static ListNode ListAdd(ListNode l1,ListNode l2){
        // 存成队列的形式
        Queue<Integer> q1 = new ArrayDeque<>();
        Queue<Integer> q2 = new ArrayDeque<>();
        while (l1!=null || l2!=null){
            if(l2 == null){
                q1.add(l1.val);
                l1 = l1.next;
            }else if(l1 == null){
                q2.add(l2.val);
                l2 = l2.next;
            }else {
                q1.add(l1.val);
                q2.add(l2.val);
                l1 = l1.next;
                l2 = l2.next;
            }
        }
        // 如果需要进位，则flag=1
        Boolean flag = false;
        ListNode result = new ListNode(-1);
        ListNode move = result;
        while (!q1.isEmpty() || !q2.isEmpty()){
            Integer poll1;
            Integer poll2;
            if(q1.isEmpty() && !q2.isEmpty()){
                poll1 = 0;
                poll2 = q2.poll();
            }else if(!q1.isEmpty() && q2.isEmpty()){
                poll1 = q1.poll();
                poll2 = 0;
            }else {
                poll1 = q1.poll();
                poll2 = q2.poll();
            }
            System.out.println("poll1 = " + poll1);
            System.out.println("poll2 = " + poll2);
            int res = poll1 + poll2;
            if (flag) {
                // 为了得到加了以后的是否要进位
                res = res + 1;
                move.next = new ListNode(res%10);
                flag = false;
            } else {
                move.next = new ListNode(res%10);
            }
            if (res > 9) {
                // 下一轮要进位，所以写在后面
                flag = true;
            }
            move = move.next;
        }
        System.out.println("flag = " + flag);
        if(flag){
            move.next = new ListNode(1);
        }
        return result.next;
    }
}
